package com.LeeCode;

/**
 * 长度为 3 的不同回文子序列
 */

public class Code1930 {
    public static void main(String[] args) {

    }

    public int countPalindromicSubsequence(String s) {
        int ans = 0;
        char[] chars = s.toCharArray();
        // 对于每个字符，找到其第一次和最后一次出现的位置
        for (char c = 'a'; c <= 'z'; c++) {
            int first = -1, last = -1;

            // 找到第一次出现位置
            for (int i = 0; i < chars.length; i++) {
                if (chars[i] == c) {
                    first = i;
                    break;
                }
            }

            if (first == -1) continue;

            // 找到最后一次出现位置
            for (int i = chars.length - 1; i > first; i--) {
                if (chars[i] == c) {
                    last = i;
                    break;
                }
            }

            if (last == -1) continue;

            // 使用位运算统计中间不同字符的个数
            int mask = 0;
            for (int i = first + 1; i < last; i++) {
                mask |= (1 << (chars[i] - 'a'));
            }

            // 计算mask中1的个数
            ans += Integer.bitCount(mask);
        }

        return ans;
    }
}
